題目連結: Sqrt(x)

題目要求為給定一非負整數 x ，要返回其平方根的整數部分。
例子1: x=4, output=2。
例子2: x=8, output=2。

思路1: 暴力法

我們可以從 i=0 開始比較 i² 與 x 的大小，若 i² < x， 則繼續往後找。若 i²=x 則返回 i 。
當 i²> x 時表示繼續往後找也都會比 x 大，直接返回 i-1。

• 複雜度評估
  當輸入的數為 Ｎ 時，最多只需要檢查 $\sqrt{N} + 1$ 次， 時間複雜度為 $O(\sqrt{N})$ 。
  此方法只用了常數量變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func mySqrt(x int) int {
    
    i:=0
 
    for i*i<=x{        
        i++
    }
     
    return i-1
}

思路2： 二分搜尋法

我們也可視為要在陣列 [0²,1²,2²,3²,...]中尋找目標數 target，因為此陣列大小有序，我們可以採用二分搜尋法，需要留意的是此陣列中不一定存在目標數。

• 複雜度評估
  當輸入的數字為 N 時，我們最多只需要 $\log_2 N + 1$ 個步驟，時間複雜度為 O(logN)。
  此方法只用了常數量變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func mySqrt(x int) int {
    
    if x<=1{
        return x
    }
    
    head:=0
    tail:=x
    mid:=0
    
    for head<tail{
        mid = head + (tail-head)/2
        
        if mid*mid==x{
            return mid
        }else if mid*mid>x{
            tail=mid
        }else{
            head=mid+1
        }
        
        
    }
    
    return tail-1
}

小結

因為 $\left( \frac{x}{2} + 1 \right) \left( \frac{x}{2} + 1 \right) = \frac{x^2}{4} + x + 1 > x$ ，我們可以將思路 2 的二分搜尋法初始查找範圍縮減在 $\left[ 0, \frac{x}{2} + 1 \right]$。
另外我們可以使用牛頓法來求解此題，牛頓法在數值分析應用相當廣泛，但使用時需留意初始值與所求之根的距離。牛頓法為產生一數列逼近所求解的過程，我們在數值分析中探討的對象為收斂速度而不是考慮時間複雜度。詳見牛頓法連結。
我們一般計算數字的平方根是會取到小數點後幾位(依需要的精度而定)，內建函式即為如此，此題也讓我們知道對求一數字的平方根開銷有多大。而在某些領域往往需要大量計算平方根倒數，此時效能就極為重要，反平方根快速演算法即應用牛頓法提升求近似值的速度，而提升的速度比起傳統方法: 先求平方根再取倒數大約快了4倍，效果顯著。

我將牛頓法作為解法 3 加上簡單的測試，上傳程式碼到此。